/**
 * 746.使用最小花费爬楼梯
 */
public class Exercise3 {
    /**
     * 以 i为开头的思想
     */
    public int minCostClimbingStair2(int[] cost) {
        // 以i位置开头
        // dp[i]: 表示从i位置，到达楼顶时，最小的花费(不包含i位置的钱)
        // 状态方程：
        // 用之前或者之后的状态推导出dp[i]的值
        // 支付dp[i]对应的cost[i]位置的钱，之后走1步到达i+1后，从i+1出发到达楼顶
        // 支付dp[i]对应的cost[i]位置的钱，之后走2步到达i+2后，从i+2出发到达楼顶
        int n = cost.length;
        // 因为不用到达n，所以不需要n位置的值，判断到n-1就可以
        int[] dp = new int[n];
        // 初始化：dp[n - 1] 和 dp[n - 2]
        dp[n - 1] = cost[n - 1];
        dp[n - 2] = cost[n - 2];
        for(int i = n - 3;i >= 0;i--){
            dp[i] = Math.min(dp[i + 1] + cost[i],dp[i + 2] + cost[i]);
        }
        return Math.min(dp[0],dp[1]);
    }

    /**
     * 以 i为结尾的思想
     */
    public int minCostClimbingStairs1(int[] cost) {
        // 以i位置结尾
        // dp[i]: 表示到达i位置时，最小的花费(不包含i位置的钱)
        // 状态方程：
        // 用之前或者之后的状态推导出dp[i]的值
        // 从i-1位置(走到i-1位置最小花费)，加上i-1位置的费用走1步
        // 从i-2位置(走到i-2位置最小花费)，加上i-2位置的费用走2步
        int n = cost.length;
        int[] dp = new int[n+1];
        // 从0或者1开始时候本身的最小花费是0
        for(int i = 2;i <= n;i++){
            dp[i] = Math.min(dp[i-1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}
